/*
 * @lc app=leetcode.cn id=97 lang=javascript
 *
 * [97] 交错字符串
 */

// @lc code=start
/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function(s1, s2, s3) {
    let n1 = s1.length, n2 = s2.length, n3 = s3.length
    if (n3 != n1 + n2) return false
    let dp = new Array(n1+1)
    for (let i = 0; i < dp.length; i++) dp[i] = new Array(n2+1)

    dp[0][0] = true

    for (let i = 0; i <= n1; i++) {
        for (let j = 0; j <= n2; j++) {
            if (i > 0) dp[i][j] = dp[i][j] || (dp[i-1][j] && s1[i-1] == s3[i+j-1])
            if (j > 0) dp[i][j] = dp[i][j] || (dp[i][j-1] && s2[j-1] == s3[i+j-1])
        }
    }
    return dp[n1][n2]
};
// @lc code=end

let s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
let re = isInterleave(s1, s2, s3)
console.log(re)